import java.util.ArrayList;
import java.util.List;

/**
* @description: 971. 翻转二叉树以匹配先序遍历
* @author hewei
* @date 2022/9/28 15:45
* @version 1.0
*/

public class FlipMatchVoyage {

    int index;
    List<Integer> ans;
    int[] voyage;
    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        this.voyage = voyage;
        index = 0;
        ans = new ArrayList<>();

        process(root);
        if (!ans.isEmpty() && ans.get(0) == -1) {
            ans.clear();
            ans.add(-1);
        }
        return ans;
    }

    public void process(TreeNode node) {
        if (node == null) return;
        if (node.val != voyage[index++]) {
            ans.clear();
            ans.add(-1);
            return;
        }
        if (index < voyage.length && node.left != null && node.left.val != voyage[index]) {
            ans.add(node.val);
            process(node.right);
            process(node.left);
        } else {
            process(node.left);
            process(node.right);
        }
    }
}